1. Field of the Invention
The present invention relates to the design of interconnection networks. More specifically, the present invention relates to a method and an apparatus for creating a robust and highly connected direct interconnection network with low diameter.
2. Related Art
Interconnection networks are widely used to integrate isolated computer system components together to form unified systems. For example, networks appear at various levels within computer systems, including: on-chip, in system interconnects, and in multi-system clusters.
In order to provide a high degree of connectivity with low communication latency, it is desirable to connect system components together into highly connected networks through direct point-to-point links. Highly connected networks have many desirable properties, including, low diameter, high bisection bandwidth, symmetry of the nodes, and high robustness with respect to link outages. Note that these properties are possible only in networks with high node degrees, which contain a large number of links.
It is also desirable for highly connected networks to be regular, scalable and have extra fabric for redundant paths between any two nodes. The latter characteristic is important for building robust, fault-tolerant networks or for networks with good load balancing properties. Note that the desired degree of redundancy largely depends on characteristics a specific network workload. Hence, it is preferable to develop a class of topologies that provide varying levels of redundancy that can be tailored for different workload requirements.
Cost and design complexity constraints can greatly affect design choices for specific network topologies. In particular, a topology with a very large number of links can be prohibitively expensive and impractical to build. Moreover, networks with large amounts of asymmetry between nodes may suffer from the complexity of the routing and from poor load balancing for some workloads.
Traditional network topologies, such as rings, meshes, and toriodal interconnects, provide only limited connectivity and consequently suffer from high network diameter and low bisection bandwidth. Hypercubes provide lower diameter and higher node degree, but still provide insufficient connectivity to satisfy large performance requirements. High fanout and fat-tree topologies do not provide desirable symmetry between nodes or low diameter (latency) and have limited robustness with respect to link outages.
What is needed is a method and an apparatus for generating highly connected networks in a manner that allows the network topology to be tuned to meet specific requirements of network usage.